#include<iostream>
#include<vector>
#include<set>
#include<functional>


using namespace std;

// 查找该数组中最小的ｋ个数
// Fun1: 快排(Ｏ(nlogn), 缺点需要改变元素组位置)　Fun2:基于大根堆的红黑数数据结构,使用STL数据容器
typedef multiset<int, greater<int> >            intSet;
typedef multiset<int, greater<int> >::iterator  setIterator;

void GetLeastNumbers_Solution2(const vector<int>& data, intSet& leastNumbers, int k)
{
    leastNumbers.clear();

    if(k < 1 || data.size() < k)
        return;

    vector<int>::const_iterator iter = data.begin();
    for(; iter != data.end(); ++ iter)
    {
        if((leastNumbers.size()) < k)
            leastNumbers.insert(*iter);

        else
        {
            setIterator iterGreatest = leastNumbers.begin();

            if(*iter < *(leastNumbers.begin()))  // 为什么这里 begin() 指向最大值？
            {
                leastNumbers.erase(iterGreatest);
                leastNumbers.insert(*iter);
            }
        }
    }
}

void print(intSet & leastNums){
	for(setIterator iter = leastNums.begin(); iter!=leastNums.end(); iter++){
		cout << *iter << "   ";
	}
	cout << endl;
}

int main(void){
intSet leastNums;
int k = 5;
	
    vector<int> data1 {4, 5, 1, 6, 2, 7, 3, 8};
   getLeastNum(data1,leastNums, k);
	print(leastNums);
    vector<int> data2 = {4, 5, 1, 6, 2, 7, 3, 8};
    getLeastNum(data2,leastNums, k);
	print(leastNums);
    vector<int> data3  = {4, 5, 1, 6, 2, 7, 3, 8};
    getLeastNum(data3,leastNums, k);
	print(leastNums);
    vector<int> data4  = {4, 5, 1, 6, 2, 7, 3, 8};
    getLeastNum(data4,leastNums, k);
	print(leastNums);
    vector<int> data5  = {4, 5, 1, 6, 2, 7, 3, 8};
    getLeastNum(data5,leastNums, k);
	print(leastNums);
    vector<int> data6  = {4, 5, 1, 6, 2, 7, 2, 8};
    getLeastNum(data6,leastNums, k);
	print(leastNums);
    int* expected = nullptr;
    getLeastNum(nullptr,leastNums, 0);
	print(leastNums);

    return 0;
}